home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group01b.txt / 000188_icon-group-sender_Thu Dec 6 08:27:25 2001.msg < prev    next >
Internet Message Format  |  2002-01-03  |  4KB
  1. Return-Path: <icon-group-sender>
  2. Received: (from root@localhost)
  3.     by baskerville.CS.Arizona.EDU (8.11.1/8.11.1) id fB6FQMU24132
  4.     for icon-group-addresses; Thu, 6 Dec 2001 08:26:22 -0700 (MST)
  5. Message-Id: <200112061526.fB6FQMU24132@baskerville.CS.Arizona.EDU>
  6. Date: Thu, 6 Dec 2001 01:18:29 -0600 (CST)
  7. From: John Paolillo <johnp@ling.uta.edu>
  8. To: eka@corp.cirrus.com, trutkin@physics.clarku.edu
  9. Subject: Re: Bio Informatics
  10. Cc: icon-group@cs.arizona.edu
  11. Errors-To: icon-group-errors@cs.arizona.edu
  12. Status: RO
  13. Content-Length: 3651
  14.  
  15. In formal-language theoretic terms, regular expressions
  16. allow the definition of finite-state transducers (FST's). These
  17. can be thought of as being described by ordinary finite
  18. state automata (FSA) with one difference, namely that they have
  19. two tapes, an input and an output tape, and state transitions
  20. can specify read-actions on the input tape and write 
  21. actions on the output tape.  Some backtracking is normally
  22. allowed.  All the same, we're pretty far down the Chomsky
  23. hierarchy in terms of computational power, with a little bit
  24. more than the ability to recognize regular languages (the
  25. term used in the Computational Linguistics literature for
  26. what FST's compute is "regular relation").  
  27.  
  28. Icon string scanning is indeed more powerful.  It is very
  29. easy to write parsers that are context-free in their 
  30. computational power, using no more than the implicit 
  31. arguments (&subject, &pos, etc.) of the scanning 
  32. environment.  When explicit argument-passing is allowed, 
  33. it becomes possible to write scanning procedures that are 
  34. context-sensitive and Turing-equivalent in their 
  35. computational power. 
  36.  
  37. So the relationship between Icon scanning and Perl regexp
  38. is that Icon is the more powerful and expressive of the two.
  39. This is both a "good" thing and a "bad" thing: scanning
  40. expressions that use the context-free or context sensitive
  41. expressivity of Icon's scanning expressions may have a
  42. worst-case exponential (i.e. intractable) complexity. FST-
  43. based scanning is generally more tractable.  If built-in 
  44. regexps are used for scanning, you are basically forced
  45. to adopt a strategy from a tractable set of computations.
  46. Not a bad thing if you are worried about performance, but 
  47. frustrating if you need the missing expressivity for 
  48. something.  
  49.  
  50. In computational linguistics, there is renewed interest in
  51. FSA and FST-based methods, on account of the tractability 
  52. issues, even though it is generally recognized that something
  53. more (what A. Joshi called "weak context sensitivity") is
  54. probably needed to adequately describe human languages.
  55. For Bio-informatics, where the main tasks are matching and
  56. assembling long gene sequences, where we don't expect to
  57. find troubling context-sensitive dependencies (if I have 
  58. such-and-such a thousand-base sequence, then I should expect
  59. an approximate copy of such-and-such another sequence over
  60. there...), FSA and FST methods are probably enough. (I doubt
  61. that anyone would have tried to use context free methods even,
  62. though I could well be wrong.)  And since Perl comes plonked 
  63. into just about any Linux or Unix installation these days,
  64. you can get going on your sequencing just by downloading a
  65. few scripts from someone's web or ftp site.  I think that
  66. would be the main reason for people using Perl (rather than,
  67. say, Java...)
  68.  
  69. Of course, one can easily write procedures for FSA and FST
  70. using Icon's string scanning (I suppose this is how the 
  71. regexp library routines work?).  This would be my preference,
  72. for purely idiosyncratic reasons.  I just think that the
  73. design of the scanning environment in Icon is an elegant
  74. and brilliant piece of work.  The use of the implicit 
  75. variables is what I would consider a revolutionary concept
  76. in programming language design. Once you understand it, 
  77. you almost never have to interact with it; it just seamlessly
  78. does its work for you while you attend to what is interesting
  79. in your program.  How unlike Prolog DCG's (which I use a lot
  80. now) or even regexps. Besides, you never know when you'll
  81. want just a little bit more expressivity...
  82.  
  83. Anyway, I hope this helps,
  84.  
  85. John Paolillo
  86. SLIS and Informatics
  87. Indiana University
  88.  
  89. http://ella.slis.indiana.edu/~paolillo/
  90.  
  91.